public class Solution148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        head = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = head, curr = head.next;
            while (curr != null) {
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode head2 = curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;
                }
                curr = next;
                prev.next = merge(head1, head2);
                while (prev.next != null) {
                    prev = prev.next;
                }
            }
        }
        return head.next;
    }

    ListNode merge(ListNode head1, ListNode head2) {
        ListNode r = new ListNode();
        ListNode t1 = head1, t2 = head2, t = r;
        while (t1 != null && t2 != null) {
            if (t1.val <= t2.val) {
                t.next = t1;
                t1 = t1.next;
            } else {
                t.next = t2;
                t2 = t2.next;
            }
            t = t.next;
        }
        t.next = t1 == null ? t2 : t1;
        return r.next;
    }
}
